def small_sum(lst, L, R):
    """
    求小和：对于数组中的每一个数字，左边所有比它小的数字的和 (利用归并排序)
    """
    if L == R:
        return 0
    mid = L + ((R - L) >> 1)
    return small_sum(lst, L, mid) + small_sum(lst, mid + 1, R) + process(lst, L, mid, R)


def process(lst, L, mid, R):
    tmp_lst = []
    sum = 0
    p, q = L, mid + 1
    while p <= mid and q <= R:
        if lst[p] < lst[q]:
            sum += lst[p] * (R - q + 1)
            tmp_lst.append(lst[p])
            p += 1
        else:
            tmp_lst.append(lst[q])
            q += 1
    while p <= L:
        tmp_lst.append(lst[p])
        p += 1
    while q <= L:
        tmp_lst.append(lst[q])
        q += 1

    for i in range(len(tmp_lst)):
        lst[L + i] = tmp_lst[i]

    return sum


if __name__ == "__main__":
    arr = [4, 2, 6, 1, 9, 5]
    print(small_sum(arr, 0, len(arr)-1))
